package leetcode.p483;

/**
 * @author: trtan
 * @date: 2021-06-18 12:17
 **/
public class SmallestGoodBase {
    public static void main(String[] args) {
        System.out.println(new SmallestGoodBase().smallestGoodBase("1000000000000000000"));
    }
    /**
     *
     * @param n
     * @return java.lang.String
     * @author trtan
     * @date 2021/6/18 13:27
     */
    public String smallestGoodBase(String n) {
        long R = Long.parseLong(n);
        int t = 0;
        // 计算当2进制时，需要多少位
        while ((1L << t) < R) {
            t++;
        }
        //从大到小枚举位数， 由于位数越多进制数x越小，所以一旦找到答案就不需要继续判断了
        for (int i = t; i >= 1; i--) {
            long l = 2, r = R - 1;
            // i位时最少可以用几进制表示
            while (l <= r) {
                long mid = (l + r) / 2;
                long d = check(i, mid, R);
                //判断差值大于0还是小于0 若大于0说明mid进制偏小可以调整l，否则调整r
                if (d == 0) {
                    return String.valueOf(mid);
                } else if (d < 0) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
        }
        return String.valueOf(R - 1);
    }

    /**
     * 计算当有t个1时，target和它x进制的差值
     * @param t 几位数（几个1）
     * @param x 几进制
     * @param target n
     * @return int
     * @author trtan
     * @date 2021/6/18 12:26
     */
    long check(int t, long x, long target) {
        int p = t;
        int k = 0;
        long tmp = target;
        while (tmp >= x) {
            tmp /= x;
            k++;
        }
        if (k < t - 1) {
            return -1;
        }
        long y = 1;
        while (t > 0) {
            target -= y;
            if (target < 0) {
                return target;
            }
            y *= x;
            t--;
        }
        return target;
    }
}
